package com.ztom.daily.n2022.m4;

/**
 * 区间和检索 - 数组可修改
 * <p>
 * https://leetcode-cn.com/problems/range-sum-query-mutable/
 *
 * @author ZhangTao
 */
public class Day04NumArray {

    /**
     * 线段树
     */
    class NumArray1 {

        private final int[] tree;
        private final int[] sum;
        private final int[] change;
        private final boolean[] update;

        public NumArray1(int[] nums) {
            // 0 位置弃而不用
            int len = nums.length + 1;

            tree = new int[len];
            System.arraycopy(nums, 0, tree, 1, nums.length);

            sum = new int[len << 2];
            change = new int[len << 2];
            update = new boolean[len << 2];
            build(1, nums.length, 1);
        }

        private void build(int l, int r, int index) {
            if (l == r) {
                sum[index] = tree[l];
                return;
            }
            int mid = l + ((r - l) >> 1);
            build(l, mid, index << 1);
            build(mid + 1, r, index << 1 | 1);

            pushUp(index);
        }

        private void pushUp(int index) {
            sum[index] = sum[index << 1] + sum[index << 1 | 1];
        }

        private void pushDown(int index, int ln, int rn) {
            if (update[index]) {
                update[index] = false;

                int l = index << 1;
                int r = index << 1 | 1;
                update[l] = true;
                update[r] = true;
                change[l] = change[index];
                change[r] = change[index];

                sum[l] = change[l] * ln;
                sum[r] = change[r] * rn;
            }
        }

        private void update(int left, int right, int val, int l, int r, int index) {
            // 无效范围
            if (left > r || right < l) {
                return;
            }

            // 全包
            if (left <= l && right >= r) {
                change[index] = val;
                update[index] = true;
                sum[index] = val * (r - l + 1);
                return;
            }

            int mid = l + ((r - l) >> 1);
            pushDown(index, mid - l + 1, r - mid);
            if (left <= mid) {
                update(left, right, val, l, mid, index << 1);
            }
            if (right > mid) {
                update(left, right, val, mid + 1, r, index << 1 | 1);
            }
            pushUp(index);
        }

        private int query(int left, int right, int l, int r, int index) {
            // 无效范围
            if (left > r || right < l) {
                return -1;
            }

            if (left <= l && right >= r) {
                return sum[index];
            }

            int mid = l + ((r - l) >> 1);
            pushDown(index, mid - l + 1, r - mid);

            int res = 0;
            if (left <= mid) {
                res += query(left, right, l, mid, index << 1);
            }
            if (right > mid) {
                res += query(left, right, mid + 1, r, index << 1 | 1);
            }

            return res;
        }

        public void update(int index, int val) {
            // 角标从 1 开始的
            update(index + 1, index + 1, val, 1, tree.length - 1, 1);
        }

        public int sumRange(int left, int right) {
            // 角标从 1 开始的
            return query(left + 1, right + 1, 1, tree.length - 1, 1);
        }
    }

    public static void main(String[] args) {

        int[] nums = {1, 3, 5};
        NumArray array = new NumArray(nums);
        System.out.println(array.sumRange(0, 2));
        array.update(1, 2);
        System.out.println(array.sumRange(0, 2));
    }

    /**
     * indexTree
     */
    static class NumArray {

        private final int[] arr;

        private final int[] tree;

        private final int size;

        public NumArray(int[] nums) {
            this.size = nums.length;
            // 0 位置弃而不用
            this.tree = new int[size + 1];
            this.arr = new int[size];
            System.arraycopy(nums, 0, arr, 0, nums.length);
            for (int i = 0; i < nums.length; i++) {
                this.add(i + 1, nums[i]);
            }
        }

        private void add(int index, int val) {
            while (index <= size) {
                tree[index] += val;
                index += index & -index;
            }
        }

        public void update(int index, int val) {
            // 先取出原值, 算出更新量
            int o = arr[index];
            arr[index] = val;
            this.add(index, val - o);
        }

        public int sumRange(int left, int right) {
            return sum(right) - sum(left - 1);
        }

        private int sum(int index) {
            int res = 0;
            index++;
            while (index > 0) {
                res += tree[index];
                index -= index & -index;
            }
            return res;
        }
    }
}
